package leetcode.editor.cn.q1_300.q100;

import java.util.Arrays;

/**
 * @author qidi
 * @date 2022-01-13 13:21:08
 */
class Q0134_GasStation {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            if (gas.length == 0 || Arrays.stream(gas).sum() < Arrays.stream(cost).sum()) return -1;

            int len = gas.length;
            int[] remains = new int[len];
            for (int i = 0; i < len; i++) {
                remains[i] = gas[i] - cost[i];
            }

            int i = 0;
            int sum = 0;
            int ans = 0;
            while (i < len) {
                sum += remains[i];
                if (sum < 0) {
                    while (i < len && remains[i] < 0) {
                        i++;
                    }
                    sum = remains[i];
                    ans = i;
                }
                i++;
            }

            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0134_GasStation().new Solution();
        System.out.println(solution.canCompleteCircuit(new int[]{5, 8, 2, 8}, new int[]{6, 5, 6, 6}));
        System.out.println(solution.canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}));
    }
}